from pqueue import PQueue

def Dijkstra(graph, start, end):
	"""Dijkstra - wyszukiwanie najkrotszej sciezki w grafie."""
	distance = {}
	known = {}
	predecessor = {}
	
	distance[start] = 0
	
	pqueue = PQueue()
	pqueue.insert((start, 0))
	
	while not pqueue.is_empty():
		first = pqueue.remove()
		if first[0] not in known:
			known[first[0]] = True
				
			edges = graph[first[0]]
			for x in edges:
				d = distance[first[0]] + x[1]
				if x[0] not in distance or distance[x[0]] > d:
					distance[x[0]] = d
					predecessor[x[0]] = first[0]
					pqueue.insert((x[0], d))

	return (distance[end], predecessor)
		
def getPath(predecessor, end):
	"""Dijkstra - odtworzenie sciezki."""
	next = end
	path = [end]

	while next in predecessor:
		next = predecessor[next]
		path.append(next)
	path.reverse()
	return " -> ".join(path)